<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-29.html">previous</a></span><span>, <a href="book-Z-H-31.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_chap_5"></a>
<h1 class=chapter>
<div class=chapterheading><a href="book-Z-H-4.html#%_toc_%_chap_5">Chapter 5</a></div><p>
<a href="book-Z-H-4.html#%_toc_%_chap_5">Computing with Register Machines</a></h1><p>

<p>
<div align=right> 
<table width=60%><tr><td>
<span class=epigraph>
<p>

My aim is to show that the heavenly machine is not a kind of divine,
live being, but a kind of clockwork (and he who believes that a clock
has soul attributes the maker's glory to the work), insofar as nearly
all the manifold motions are caused by a most simple and material
force, just as all motions of the clock are caused by a single weight.<p>

<a name="%_idx_5456"></a>Johannes Kepler (letter to Herwart von Hohenburg, 1605)<p>

</span>
</td></tr></table>
</div>

<p><p>


We began this book by studying processes and by describing processes
in terms of procedures written in Lisp.  To explain the meanings of
these procedures, we used a succession of models of evaluation: the
substitution model of chapter&nbsp;1, the environment model of chapter&nbsp;3,
and the metacircular evaluator of chapter&nbsp;4.  Our examination of the
metacircular evaluator, in particular, dispelled much of the mystery
of how Lisp-like languages are interpreted.
But even the metacircular evaluator leaves important questions
unanswered, because it fails to elucidate the mechanisms of control in
a Lisp system.  For instance, the evaluator does not explain how the
evaluation of a subexpression manages to return a value to the
expression that uses this value, nor does the evaluator explain how
some recursive procedures generate iterative processes (that is, are evaluated
using constant space) whereas other recursive procedures generate recursive
processes.  These questions remain unanswered because the metacircular
evaluator is itself a Lisp program and hence inherits the control
structure of the underlying Lisp system.  In order to provide a more
complete description of the control structure of the Lisp evaluator,
we must work at a more primitive level than Lisp itself.<p>

In this chapter we will describe processes in terms of the step-by-step
operation of a traditional computer.  Such a computer, or <a name="%_idx_5458"></a><em>register
machine</em>, sequentially executes <em>instructions</em> that
manipulate the contents of a fixed set of storage elements called <a name="%_idx_5460"></a><em>registers</em>.  A typical register-machine instruction applies a
primitive operation to the contents of some registers and assigns the
result to another register.  Our descriptions of processes executed by
register machines will look very much like ``machine-language''
programs for traditional computers.  However, instead of focusing on
the machine language of any particular computer, we will examine
several Lisp procedures and design a specific register machine to
execute each procedure.  Thus, we will approach our task from the
perspective of a hardware architect rather than that of a
machine-language computer programmer.  In designing register machines,
we will develop mechanisms for implementing important programming
constructs such as recursion.  We will also present a language for
describing designs for register machines.  In
section&nbsp;<a href="book-Z-H-32.html#%_sec_5.2">5.2</a> we will
implement a Lisp program that
uses these descriptions to simulate the machines we design.<p>

Most of the primitive operations of our register machines are very
simple.  For example, an operation might add the numbers fetched from
two registers, producing a result to be stored into a third register.
Such an operation can be performed by easily described hardware.  In
order to deal with list structure, however, we will also use the
memory operations <tt>car</tt>, <tt>cdr</tt>, and <tt>cons</tt>, which require
an elaborate storage-allocation mechanism.  In
section&nbsp;<a href="book-Z-H-33.html#%_sec_5.3">5.3</a> we study their implementation in
terms of more elementary operations.<p>

In section&nbsp;<a href="book-Z-H-34.html#%_sec_5.4">5.4</a>, after we have accumulated experience
formulating simple procedures as register machines, we will design a
machine that carries out the algorithm described by the metacircular
evaluator of section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1">4.1</a>.  This will fill in the gap in
our understanding of how Scheme expressions are interpreted, by
providing an explicit model for the mechanisms of control in the
evaluator.
In section&nbsp;<a href="book-Z-H-35.html#%_sec_5.5">5.5</a> we will study a simple compiler that
translates Scheme programs into sequences of instructions that can be
executed directly with the registers and operations of the evaluator
register machine.<p>


<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-29.html">previous</a></span><span>, <a href="book-Z-H-31.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
